Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 3 на тему: " Структура даних СТЕК" з дисципліни: " Програмування. Частина III. Структури даних та алгоритми " Вибір варіанта індивідуального завдання: № варіанта = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 21+1=(13+66)% 21+1=79%21+1=16+1=17  Мета роботи Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. Постановка задачі Змоделювати стек на базі статичного масиву згідно з завданням. Написати основні операції для роботи зі стеком (push, pop, top, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) різних цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стека під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості стеку" (stack underflow) та "переповнення стеку" (stack overflow). Зауваження: працювати зі стеком як з абстрактним типом даних (АТД), а не як з масивом 17. Реалізувати стек за допомогою масива data[N], в якому останній елемент масива, а не окрема змiнна, використовуєтся для зберiгання покажчика вершини стека, а решта елементів масива можуть містити елементи самого стека. Після обробки всієї заданої вхідної послідовності перетворити отриманий стек так, щоб він не містив однакових елементів, що йдуть підряд (тобто замість кожної послідовності однакових елементів має залишитись тільки один елемент, наприклад, зі стеку з вмістом 22230115555 треба отримати стек з вмістом 23015). 3. Динаміка вмісту стеку (або масиву) 3.1. Послідовність 10 цілих (додатніх, від'ємних, нульових, парних і непарних) чисел -3; 2; 2; 2; 0; 7; -9; -4; 5; 5; 3.2. Схематичне зображення стеку після обробки кожного числа з вхідної послідовності
3.3. Вибрати один з варіантів у відповідності до завдання: Згідно умови,після обробки вхідної послідовності потрібно перетворити стек так,щоб він не містив однакових елементів,що йдуть підряд. Замість кожної послідовності однакових елементів має залишитись тільки один елемент. В задані послідовності є елементи що йдуть підряд-дві “2” і дві “5” . -3; 2; 2; 2; 0; 7; -9; -4; 5; 5
 4. Алгоритм розв’язання задачі ШАБЛОННИЙ ПАРАМЕТР, ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ класу Stack<T> Шаблонний параметр T предтставляє собою тип елементів, що зберігаються у стеку. Він може бути довільним вбудованим типом в мові С++ а також структурою, класом (в якому визначений конструктор по замовчуванню),конструктор копіювання і оператор присвоєння. Stack<T>:: CAPACITY предтаставляє максимальну кількість елементів довільного стеку (як тільки ця кількість буде досягнута, додавання елементів у стек припиняється). КОНСТРУКТОР ШАБЛОННОГО КЛАСУ Stack<Т> Stack() Післяумова: стек ініціалізується порожнім МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ шаблонного класу stack<Item>: void push(const T & k) Передумова: size( ) < CAPACITY. Післяумова: в стек занесена нова копія елемента. void pop( ) Передумова: size( ) > 0. Післяумова: вилучена вершина стека. КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ шаблонного класу Stack<T>: T top() const Передумова: size( ) > 0. Післяумова: повертається вершина стека, однак стек при цьому не змінюється. Цим цей клас дещо відрізняється від стека, що описаний в стандартній бібліотеці шаблонів STL ( в якому функція top повертає посилання на елемент, що знаходиться у вершині стека). bool empty( ) const Післяумова: повертає значення true, якщо стек порожній, і значення false, якщо це не так. 5. Результати викон...